home *** CD-ROM | disk | FTP | other *** search
/ Inside Multimedia 1994 April / Inside Multimedia CD-ROM (April 1994).iso / prg / gs / gssource.exe / SLZWD.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-24  |  6.8 KB  |  229 lines
  1. /* Copyright (C) 1991, 1992 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* slzwd.c */
  21. /* LZW decoding filter */
  22. #include <stdio.h>
  23. #include "std.h"
  24. #include "gdebug.h"
  25. #include "stream.h"
  26.  
  27. /********************************************************/
  28. /* LZW routines are based on:                */
  29. /* Dr. Dobbs Journal --- Oct. 1989.             */
  30. /* Article on LZW Data Compression by Mark R. Nelson     */
  31. /********************************************************/
  32.  
  33. /*
  34.  * This code implements enhancements to the LZW algorithm.
  35.  * For a full explanation of the algorithm, see the file slzwe.c.
  36.  */
  37.  
  38. /* Define the special codes */
  39. #define code_reset 256
  40. #define code_eod 257
  41. #define code_0 258            /* first assignable code */
  42.  
  43. /* ------ LZWDecode filter ------ */
  44.  
  45. typedef struct lzw_decode_s {
  46.     byte datum;
  47.     byte len;            /* length of code */
  48.     ushort prefix;            /* code to be prefixed */
  49. } lzw_decode;
  50. #define lzw_decode_max 4096        /* must be 4096 */
  51.  
  52. typedef struct lzw_decode_table_s {
  53.     lzw_decode decode[lzw_decode_max+1];
  54. } lzw_decode_table;
  55.  
  56. /* Export the size of the LZW decoding table. */
  57. const uint s_LZWD_table_sizeof = sizeof(lzw_decode_table);
  58.  
  59. /* Initialize LZWDecode filter */
  60. void
  61. s_LZWD_init(register stream *s, lzw_decode_table *table, int enhanced)
  62. {    register lzw_decode *dc;
  63.     register int i;
  64.     s->lzws.bits_left = 0;
  65.     s->lzws.next_code = code_0;
  66.     s->lzws.code_size = 9;
  67.     s->lzws.prev_code = -1;
  68.     s->odd = -1;
  69.     s->lzws.enhanced = enhanced;
  70.     s->lzws.decode_table = table;
  71.     dc = table->decode;
  72.     dc[code_reset].len = 255;
  73.     dc[code_eod].len = 255;
  74.     for ( i = 0; i < 256; i++, dc++ )
  75.       dc->datum = i, dc->len = 1, dc->prefix = code_eod;
  76. }
  77.  
  78. /* Buffer refill for LZWDecode filter */
  79. /****** DOESN'T HANDLE CODES LONGER THAN THE BUFFER SIZE ******/
  80. private int
  81. s_LZWD_read_buf(register stream *s)
  82. {    int code = s->odd;
  83.     int prev_code = s->lzws.prev_code;
  84.     byte bits = s->lzws.bits;
  85.     int bits_left = s->lzws.bits_left;
  86.     int code_size = s->lzws.code_size;    /* cache only */
  87.     int code_mask = (1 << code_size) - 1;
  88.     int next_code = s->lzws.next_code;
  89.     register stream *strm = s->strm;
  90.     register byte *p = s->cbuf;
  91.     byte *limit = p + s->bsize;
  92.     lzw_decode *table = s->lzws.decode_table->decode;
  93.     lzw_decode *dc_next = table + next_code;
  94.     int enhanced = s->lzws.enhanced;
  95.     lzw_decode *dc;
  96.     uint prev_len, len;
  97.     int c;
  98.     byte *p1;
  99.     if ( prev_code >= 0 )
  100.         prev_len = table[prev_code].len;
  101.     if ( code >= 0 ) goto add;
  102. top:    code = bits << (code_size - bits_left);
  103.     bits = sgetc(strm);
  104.     if ( (bits_left += 8 - code_size) < 0 )
  105.        {    code += bits << -bits_left;
  106.         bits = sgetc(strm);
  107.         bits_left += 8;
  108.        }
  109.     code = (code + (bits >> bits_left)) & code_mask;
  110. #ifdef DEBUG
  111. if ( gs_debug['w'] )
  112.     dprintf2("[w]reading 0x%x,%d", code, code_size);
  113. #endif
  114.     /* Invert the code-shortening algorithm described in slzwd.c. */
  115.     if ( enhanced )
  116.        {    uint N = code_mask + 1;
  117.         uint M = (prev_code < 0 ? next_code : next_code + 1);
  118.         uint D = N - M;
  119.         if ( code < D << 1 )    /* S-1 bits */
  120.             code >>= 1, ++bits_left;
  121.         else if ( !(code & 1) )    /* S bits, < N/2 */
  122.             code >>= 1;
  123.         else            /* S bits, >= N/2 */
  124.             code = (code >> 1) - N / 2 + M;
  125. #ifdef DEBUG
  126. if ( gs_debug['w'] )
  127.    {    if ( enhanced )
  128.         dprintf2(" -> 0x%x,%d", code,
  129.              (code < D ? code_size - 1 : code_size));
  130.    }
  131. #endif
  132.        }
  133. #ifdef DEBUG
  134. if ( gs_debug['w'] )
  135.     dputc('\n');
  136. #endif
  137. add:    /*
  138.      * There is an anomalous case where a code S is followed
  139.      * immediately by another occurrence of the S string.
  140.      * In this case, the next available code will be defined as
  141.      * S followed by the first character of S, and will be
  142.      * emitted immediately after the code S.  We have to
  143.      * recognize this case specially, by noting that the code is
  144.      * equal to next_code.
  145.      */
  146.     if ( code == next_code )
  147.        {    /* Fabricate the entry for the code.  It will be */
  148.         /* overwritten immediately, of course. */
  149.         for ( c = prev_code; c != code_eod; c = table[c].prefix )
  150.             dc_next->datum = c;
  151.         len = prev_len + 1;
  152.         dc_next->len = min(len, 255);
  153.         dc_next->prefix = prev_code;
  154. #ifdef DEBUG
  155. if ( gs_debug['w'] )
  156.         dprintf3("[w]decoding anomalous 0x%x=0x%x+%c\n",
  157.                  next_code, prev_code, dc_next->datum);
  158. #endif
  159.        }
  160.     /* See if there is enough room for the code. */
  161.     len = table[code].len;
  162.     if ( len == 255 )
  163.        {    /* Check for special code (reset or end). */
  164.         /* We set their lengths to 255 to avoid doing */
  165.         /* an extra check in the normal case. */
  166.         switch ( code )
  167.            {
  168.         case code_reset:
  169.             next_code = code_0;
  170.             dc_next = table + code_0;
  171.             s->lzws.code_size = code_size = 9;
  172.             code_mask = (1 << 9) - 1;
  173.             prev_code = -1;
  174.             goto top;
  175.         case code_eod:
  176.             s->end_status = EOFC;
  177.             goto out;
  178.            }
  179.         /* The code length won't fit in a byte, */
  180.         /* compute it the hard way. */
  181.         for ( c = code, len = 0; c != code_eod; len++ )
  182.             c = table[c].prefix;
  183.        }
  184.     if ( limit - p < len )
  185.        {    s->odd = code;
  186.         goto out;
  187.        }
  188.     /* Copy the string to the buffer (back to front). */
  189.     c = code;
  190.     p1 = p += len;
  191.     do
  192.        {    *--p1 = (dc = &table[c])->datum;
  193.        }
  194.     while ( (c = dc->prefix) != code_eod );
  195.     /* Add a new entry to the table */
  196.     if ( prev_code >= 0 )
  197.        {    dc_next->datum = *p1;    /* first char of string */
  198.         ++prev_len;
  199.         dc_next->len = min(prev_len, 255);
  200.         dc_next->prefix = prev_code;
  201.         dc_next++;
  202. #ifdef DEBUG
  203. if ( gs_debug['w'] )
  204.         dprintf4("[w]decoding 0x%x=0x%x+%c(%d)\n",
  205.                  next_code, prev_code, *p1, min(len, 255));
  206. #endif
  207.         if ( ++next_code == code_mask )
  208.             /* Crossed a power of 2 */
  209.             code_size = ++(s->lzws.code_size),
  210.             code_mask = (1 << code_size) - 1;
  211.        }
  212.     prev_code = code;
  213.     prev_len = len;
  214.     goto top;
  215. out:    s->cptr = s->cbuf - 1;
  216.     s->endptr = p - 1;
  217.     s->lzws.prev_code = prev_code;
  218.     s->lzws.bits = bits;
  219.     s->lzws.bits_left = bits_left;
  220.     s->lzws.next_code = next_code;
  221.     return 0;
  222. }
  223.  
  224. /* Stream procedures */
  225. const stream_procs s_LZWD_procs =
  226.    {    s_std_noavailable, NULL, s_std_read_flush, s_std_close,
  227.     s_LZWD_read_buf, NULL
  228.    };
  229.